package ua.yandex.mergesort;

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class MergeSort {

    private final ExecutorService service;

    MergeSort() {
        service = Executors.newCachedThreadPool();
    }

    private long[] merge(long[] a, long[] b) {
        long[] res = new long[a.length + b.length];
        int ia = 0, ib = 0;
        for (int i = 0; i < res.length; i++) {
            if ((ib == b.length) || (ia < a.length && a[ia] <= b[ib])) {
                res[i] = a[ia];
                ia++;
            } else {
                res[i] = b[ib];
                ib++;
            }
        }
        return res;
    }

    public long[] sort(long[] s) throws InterruptedException,
            ExecutionException {
        if (s.length <= 1) {
            return s;
        }
        int m = (int) s.length / 2;
        long[] a = new long[m];
        long[] b = new long[s.length - m];
        System.arraycopy(s, 0, a, 0, m);
        System.arraycopy(s, m, b, 0, s.length - m);
        MyCallable r = new MyCallable(a);
        Future<long[]> result = service.submit(r);
        b = sort(b);
        while (!result.isDone());
        a = result.get();
        return merge(a, b);
    }

    public class MyCallable implements Callable<long[]> {

        private final long[] a;

        MyCallable(long[] ar) {
            a = new long[ar.length];
            System.arraycopy(ar, 0, a, 0, ar.length);
        }

        @Override
        public long[] call() throws InterruptedException, ExecutionException {
            return sort(a);
        }
    }
}
